//class Solution {
//public:
//    vector<int> preorderTraversal(TreeNode* root) {
//        vector<int> ret;
//        if (root == nullptr) return ret;
//
//        TreeNode* cur = root, * prev = nullptr;
//        while (cur)
//        {
//            if (cur->left == nullptr)
//            {
//                ret.push_back(cur->val);
//                cur = cur->right;
//            }
//            else
//            {
//                prev = cur->left;
//                while (prev->right != nullptr && prev->right != cur)
//                    prev = prev->right;
//                if (prev->right == nullptr)
//                {
//                    prev->right = cur;
//                    ret.push_back(cur->val);
//                    cur = cur->left;
//                }
//                else
//                {
//                    prev->right = nullptr;
//                    cur = cur->right;
//                }
//            }
//        }
//        return ret;
//    }
//};


//class Solution {
//public:
//    vector<int> preorderTraversal(TreeNode* root) {
//        vector<int> ret;
//        if (root == nullptr) return ret;
//
//        stack<TreeNode*> st;
//        st.push(root);
//        while (!st.empty())
//        {
//            TreeNode* cur = st.top();
//            st.pop();
//            ret.push_back(cur->val);
//            if (cur->right)
//                st.push(cur->right);
//            if (cur->left)
//                st.push(cur->left);
//        }
//        return ret;
//    }
//};



//class Solution {
//public:
//    vector<int> ret;
//    vector<int> preorderTraversal(TreeNode* root) {
//        dfs(root);
//        return ret;
//    }
//
//    void dfs(TreeNode* root)
//    {
//        if (root == nullptr) return;
//        ret.push_back(root->val);
//        dfs(root->left);
//        dfs(root->right);
//    }
//};



